#include <stdio.h>

/*QuickSort*/
void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
    return;
}
void Median3(int *A, int left, int right)
{
    int mid = (left + right) / 2;
    printf("%d %d %d\n", left, mid, right);
    // printf("%d %d %d\n",A[left],A[mid],A[right]);
    if (A[left] > A[mid])
        Swap(&A[left], &A[mid]);
    // printf("%d %d %d\n",A[left],A[mid],A[right]);
    if (A[left] > A[right])
        Swap(&A[left], &A[right]);
    // printf("%d %d %d\n",A[left],A[mid],A[right]);
    if (A[mid] > A[right])
        Swap(&A[mid], &A[right]);
    // printf("%d %d %d\n",A[left],A[mid],A[right]);
    Swap(&A[mid], &A[right - 1]);
    printf("%d %d %d\n", A[left], A[mid], A[right]);
    return;
}

int Partition(int *A, int left, int right)
{
    Median3(A, left, right);
    if ((right - left) <= 1)
    {
        int i = left;
        return i;
    }
    int i = left + 1;
    int j = right - 2;
    int pivot = A[right - 1];
    while (1)
    {
        while (A[i] < pivot)
            i++;
        while (A[j] > pivot)
            j--;
        if (i < j)
        {
            Swap(&A[i], &A[j]);
            i++;
            j--;
        }
        else
        {
            break;
        }
    }
    Swap(&A[i], &A[right - 1]); // bring pivot back to middle
    return i;
}

void QuickSort(int *A, int left, int right)
{
    if (left >= right)
        return;
    int q = Partition(A, left, right);

    printf("q=%d\n", q);
    for (int i = 0; i < 10; i++)
    {
        printf("%d\t", A[i]);
    }
    printf("\n");

    QuickSort(A, left, q - 1);
    QuickSort(A, q + 1, right);
}

/*Heap Sort*/
void Insert(int *A, int size, int x)
{
    int hole = size++;
    while (hole > 0 && x > A[(hole - 1) / 2])
    {
        A[hole] = A[(hole - 1) / 2];
        hole = (hole - 1) / 2;
    }            // insert value is bigger than its parent,swap hole position and the parent
    A[hole] = x; // insert
    return;
}
int DeleteMax(int *A, int size)
{
    int max = A[0];
    int hole = 0;
    int x = A[--size];                // store last element
    while ((hole + 1) * 2 - 1 < size) // A[hole] has children
    {
        int bid;
        int child1 = (hole + 1) * 2 - 1;
        if (child1 + 1 == size) // only one child
        {
            bid = child1;
        }
        else
        {
            bid = A[child1] > A[child1 + 1] ? child1 : child1 + 1; // select the index of bigger child
        }
        if (x >= A[bid]) // insert value is bigger than child, exit loop
            break;
        // swap hole with the bigger child
        A[hole] = A[bid];
        hole = bid;
    }
    A[hole] = x; // insert
    return max;
}
void HeapSort(int *A, int size)
{
    for (int i = 0; i < size; i++)
    {
        Insert(A, i, A[i]);
    }
    for (int j = size - 1; j > 0; j--)
    {
        A[j] = DeleteMax(A, j + 1);
    }
}

int main()
{
    int A[] = {3, 2, 5, 7, 6, 8, 1, 9, 0};
    // Swap(&A[0],&A[1]);
    // printf("%d %d",A[0],A[1]);
    // Median3(A,0,9);
    // int q=Partition(A,0,9);
    // printf("q=%d\n",q);

    // QuickSort(A,0,9);
    HeapSort(A, 9);
    for (int i = 0; i < 9; i++)
    {
        printf("%d\t", A[i]);
    }
    return 0;
}